import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution886 {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        int[] first=new int[n];
        int[] next=new int[dislikes.length*2];
        int[] go=new int[dislikes.length*2];
        int[] color=new int[n];
        Arrays.fill(first,-1);
        Arrays.fill(color,-1);
        int c=0;
        for (int[] dislike : dislikes) {
            next[c]=first[dislike[0]-1];
            first[dislike[0]-1]=c;
            go[c]=dislike[1]-1;
            c++;
            next[c]=first[dislike[1]-1];
            first[dislike[1]-1]=c;
            go[c]=dislike[0]-1;
            c++;
        }
        for (int i=0;i<n;i++){
            if (color[i]==-1){
                Queue<Integer> queue=new LinkedList<>();
                queue.offer(i);
                color[i]=0;
                while (!queue.isEmpty()){
                    int k=queue.poll();
                    int p=first[k];
                    while (p!=-1){
                        int v=go[p];
                        if (color[v]==color[k]){
                            return false;
                        }
                        if (color[v]==-1){
                            queue.offer(v);
                            color[v]=1-color[k];
                        }
                        p=next[p];
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution886().possibleBipartition(4,new int[][]{{1,2},{1,3},{2,4}}));
    }
}
